package 二叉树高频题目_上_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class Code08_CompletenessOfBinaryTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    // 提交以下的方法
    // 如果测试数据量变大了就修改这个值
    public static int MAXN = 10001;
    public static TreeNode[] queue = new TreeNode[MAXN];
    public static int l, r;
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return false;
        }
        l = 0;
        r = 0;
        queue[r++] = root;
        // 是否遇到过一个节点的左右两个孩子不双全的节点
        boolean leaf = false;
        while(l < r){
            TreeNode cur = queue[l++];
            if((cur.left == null && cur.right != null) || (leaf && (cur.left != null || cur.right != null))){
                return false;
            }
            if(cur.left != null){
                queue[r++] = cur.left;
            }
            if(cur.right != null){
                queue[r++] = cur.right;
            }
            // 一个节点缺失了左右孩子节点其中一个
            if(cur.left == null || cur.right == null){
                leaf = true;
            }
        }
        return true;
    }
}
